/*
 * @lc app=leetcode.cn id=1020 lang=typescript
 *
 * [1020] 飞地的数量
 */

// @lc code=start
function numEnclaves(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dirs = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const dfs = (i: number, j: number) => {
    if (i < 0 || i >= m) return;
    if (j < 0 || j >= n) return;
    if (grid[i][j] === 0) return;
    // 已经访问过，标记为0
    grid[i][j] = 0;
    for (const [x, y] of dirs) {
      dfs(i + x, j + y);
    }
  };
  // 从所有的边界开始dfs
  for (let i = 0; i < m; i++) {
    // 第一列
    dfs(i, 0);
    // 最后一列
    dfs(i, n - 1);
  }
  for (let j = 1; j < n - 1; j++) {
    dfs(0, j);
    dfs(m - 1, j);
  }
  let ans = 0;
  // 矩阵中剩下的岛屿就是飞地
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) ans++;
    }
  }

  return ans;
}
// @lc code=end
